module CharMap = Map.Make(Char)
module CharSet = Set.Make(Char)

open Ast

(* Helper functions; see hw1.mli for documentation *)

(* You shouldn't have to modify any of these, but you may if you wish *)

let string2expr str =
  let lexbuf = Lexing.from_string str in
  Parser.expr Scanner.token lexbuf

let rec string_of_expr = function
    Id(c) -> String.make 1 c
  | And(e1, e2) -> "(" ^ string_of_expr e1 ^ string_of_expr e2 ^ ")"
  | Or(e1, e2) -> "(" ^ string_of_expr e1 ^ "+" ^ string_of_expr e2 ^ ")"
  | Not(e) -> "(!" ^ string_of_expr e ^ ")"

let binary_envs vars =
  let rec tt env = function
     v :: vs -> (tt (CharMap.add v false env) vs) @
                (tt (CharMap.add v true env) vs)
    | [] -> [env]
  in tt CharMap.empty vars

let string_of_bit b = if b then "1" else "0"


(******************************************)
(* Your solutions should start below here *)
(******************************************)



(* Problem 1: Incorrect, but type is right *)	
let rle l =
	let rec runlength t len = function
		|h::tl -> if h=t  then runlength t (len+1) tl 
							else len
		|[] -> if len<>1 then len
		       else 1
	in
	(let rec count pre num = function
		|h::tl -> if(pre = h && num<>0) then count h 1 tl 
							            else ([h, runlength h 1 tl] @ count h 1 tl)
		|[]->[]
		in 
		if l<>[] then count (List.hd l) 0 l else []);;
			

(* Problem 2a: Incorrect, but returns the correct type *)
let free_vars expr = 
	let rec count ss = function
         Id(x) -> CharSet.add x ss
       | And(e1, e2) -> count (count ss e1) e2
       | Or(e1, e2) -> count (count ss e1) e2;
       | Not(e1) -> count ss e1
  in ( CharSet.elements (count CharSet.empty expr) );;

(* Problem 2b: Incorrect, but returns the correct type *)
let eval env expr = 
	let rec calc env= function
			 Id (x) -> CharMap.find x env
			|And (e1, e2) -> (calc env e1)&&(calc env e2)
			|Or (e1, e2) -> (calc env e1)||(calc env e2)
			|Not (e1) -> not (calc env e1)
	in ( calc env expr);;

(* Problem 2c: Incorrect, but returns something that looks right *)
let string2tt str = 
	let expr = string2expr str 
	in
	(let freevar = free_vars expr 
	in
		(let env_list = binary_envs freevar 
		in
			(let rec map2string k v tl= String.concat "" (tl::[string_of_bit v])
			in
				let rec res  = function
					|env::tl -> String.concat "" ((CharMap.fold map2string env "")::" "::string_of_bit (eval env expr)::"\n"::(res tl)::[])
					|[] -> ""
					in res env_list )));;





